Năm thứ 3 (676), Thổ Phồn xâm phạm, triều đình giáng chiếu cho Hành Kiệm làm Thao Châu đạo Tả nhị quân tổng quản, ít lâu sau được làm Thái Châu Trấn phủ Hữu quân tổng quản, đều chịu sự chỉ huy của Chu vương Lý Hiển. Năm Nghi Phượng thứ 2 (677), [lower-alpha 4] Đột Quyết Thập Tính khả hãn A Sử Na Đô Chi cùng thủ lãnh Lý Già Bặc dẫn dụ các bộ lạc khác họ (phồn lạc) [lower-alpha 5] xâm phạm An Tây, liên minh với Thổ Phồn. Tháng 6 ÂL năm Điều Lộ đầu tiên (679), [lower-alpha 6] có người đề nghị phát binh đánh dẹp, Hành Kiệm nhắc lại thất bại của bọn Lý Kính Huyền, Lưu Thẩm Lễ năm ngoái [lower-alpha 7], cho rằng lúc này không thể tiếp tục dùng binh. Hành Kiệm đề xuất đưa con tin Ba Tư là vương tử Nê Niết Sư (Narsieh) về nối ngôi [lower-alpha 8], mượn đường đi qua 2 bộ lạc của bọn A Sử Na Đô Chi, tùy nghi hành động, làm ít được nhiều. Cao Tông nghe theo, mệnh cho Hành Kiệm đưa con tin lên đường, còn được làm An phủ Đại Thực sứ. [1] [2]

Sứ đoàn đi vào sa mạc Mạc Hạ Duyên Thích [lower-alpha 9], gặp lúc cát bay đá chạy, trời đất tối tăm, người dẫn đường cũng lạc lối, tướng sĩ đều chịu đói khát. Hành Kiệm lệnh cho hạ trại, thành kính cúng tế, rồi nói cả đoàn: “Suối nước cách đây không xa.” Ít lâu sau mây tan gió lặng, đi thêm vài trăm bước, gặp nước – cỏ rất tốt tươi, chẳng ai biết đây là nơi nào. Mọi người đều khâm phục, sánh Hành Kiệm với Nhị sư tướng quân nhà Hán (tức Lý Quảng Lợi). Sứ đoàn đến Tây Châu [lower-alpha 10], được các tộc thiểu số đón tiếp trọng thể; Hành Kiệm chiêu mộ hơn ngàn thanh niên địa phương theo mình tây tiến, đánh tiếng rằng lúc này khí hậu nóng nhất, đợi sang mùa thu mắt mẻ mới lên đường. A Sử Na Đô Chi dò biết được, nên không phòng bị. Hành Kiệm thong thả triệu tù trưởng các tộc ở 4 trấn Quy Tư, Vu Điền, Sơ Lặc, Toái Diệp, thông báo tổ chức chuyến đi bắn, chiêu mộ gần vạn con em tù trưởng các tộc. Hành Kiệm bày cuộc săn giả, chỉnh đốn đội ngũ, sau vài ngày, theo đường ắt mà đi. Còn cách bộ lạc của A Sử Na Đô Chi hơn 10 dặm, Hành Kiệm trước tiên sai người thân cận của Đô Chi đến trấn an ông ta, nói mình nhàn rỗi ra ngoài, chứ chẳng phải đánh dẹp gì. Sau đó Hành Kiệm sai sứ giải triệu Đô Chi đến gặp mặt. Đô Chi vốn cùng Lý Già Bặc mưu tính cự tuyệt sứ giả nhà Đường sẽ đến vào mùa thu, chợt nghe tin quân triều đình đến, không biết làm sao, tự soái 500 con em cưỡi ngựa đến doanh trại của Hành Kiệm, lập tức bị bắt giữ. Hôm ấy, Hành Kiệm lấy Khế tiễn (mũi tên ước hẹn) của Đô Chi gọi tù trưởng tất cả bộ lạc đến nghe lệnh, rồi bắt họ đưa về thành Toái Diệp. [1] [2]

Hành Kiệm chọn kỵ binh tinh nhuệ, đem theo hành trang gọn nhẹ, đi suốt ngày đêm, muốn tập kích Lý Già Bặc. Giữa đường Hành Kiệm bắt được sứ giả của A Sử Na Đô Chi đang quay về, đồng hành với sứ giả của Già Bặc. Hành Kiệm phóng thích sứ giả của Già Bặc, lệnh cho hắn thông báo cho chủ nhân về việc Đô Chi đã bị bắt; ngay sau đó Già Bặc đến xin hàng. Vì thế quan tướng dưới quyền Hành Kiệm đã lập bia ở thành Toái Diệp, để kỷ niệm công lao của ông. Hành Kiệm đem Đô Chi, Già Bặc về kinh sư, Đường Cao Tông đích thân mở tiệc úy lạo, nói: “Hành Kiệm đem một cánh quân cô độc, vào sâu muôn dặm, binh khí không vấy máu mà bắt giữ loạn đảng, có thể nói là văn võ kiêm bị vậy. Nay cho khanh nhận cả hai chức.” Ngay hôm ấy Cao Tông bái Hành Kiệm làm Lễ bộ thượng thư, kiêm Kiểm hiệu Hữu vệ đại tướng quân. [1] [2]

Cùng năm, thủ lãnh Đột Quyết là A Sử Đức Ôn Phó nổi dậy, 24 châu dưới quyền quản hạt của Thiền Vu đô hộ phủ hưởng ứng, lực lượng lên đến vài mươi vạn người. Thiền Vu đô hộ Tiêu Tự Nghiệp soái binh đánh dẹp nhưng thất bại, vì thế triều đình lấy Hành Kiệm làm Định Tương đạo Hành quân đại tổng quản, soái bọn Thái phó thiếu khanh Lý Tư Văn, Doanh Châu đô đốc Chu Đạo Vụ đem 18 vạn bộ binh, hợp với Trình Vụ Đĩnh đem quân Tây lộ, Lý Văn Giản đem quân Đông lộ, cả thảy hơn 30 vạn, cờ xí kéo dài mấy ngàn dặm, đều chịu sự chỉ huy của ông. [1] [2] Đời Đường ra quân rầm rộ như vậy, có thể nói là chưa từng có. [1]

Hành Kiệm hành quân đến Sóc Châu, biết lương thực của Tiêu Tự Nghiệp mấy lần bị chặn cướp, binh sĩ phần nhiều bị chết đói. Hành Kiệm làm giả 300 cỗ xe chở lương, mỗi xe giấu 5 tráng sĩ, đem theo mạch đao, nỏ cứng, lấy vài trăm binh sĩ gầy yếu kéo xe, lại cho tinh binh theo sau. Đoàn xe đi vào nơi hiểm trở để chờ địch. Quả nhiên phản quân tràn xuống, lính kéo xe tan chạy. Người Đột Quyết ruổi xe đến nơi có nước và cỏ, cởi yên chăn ngựa, đang muốn lấy lương thực trong xe, đột nhiên tráng sĩ cùng nhau xông ra, phục binh cũng đến, bắt giết gần sạch, tàn dư tan chạy. Từ ấy xe lương của quân Đường, không ai dám đến gần. [1] [2]

Quân Đường đến bắc biên của Thiền Vu đô hộ phủ, gặp lúc trời chiều, bèn hạ trại. Hào lũy đã xong, Hành Kiệm chợt ra lệnh dời lên đồi cao, tướng sĩ đều nói binh sĩ đã ổn định, không nên khiến họ vất vả rối ren nữa; ông không nghe, lại càng thúc giục họ di chuyển. Đêm ấy, mưa bão kéo đến, nơi hạ trại cũ ngập dưới nước hơn trượng, tướng sĩ chẳng ai không thán phục, hỏi làm sao biết được, Hành Kiệm đáp: “Từ nay cứ nghe mệnh lệnh của ta, chứ đừng hỏi làm sao ta biết.” [1] [2]

Quân Đột Quyết kháng cự ở Hắc Sơn [lower-alpha 11], quân Đường liên tiếp giành thắng lợi, trước sau giết địch không đếm xuể. Khả hãn được phản quân đề cử là A Sử Na Nê Thục Bặc bị bộ hạ giết chết, đem đầu ông ta đến xin hàng; quân Đường lại bắt được 1 thủ lãnh trọng yếu của phản quân là A Sử Na Phụng Chức đem về kinh sư. Tàn quân Đột Quyết trốn đi Lang Sơn. Sau khi Hành Kiệm về triều, A Sử Na Phục Niệm tự xưng khả hãn, hội họp với A Sử Đức Ôn Phó, tập hợp lực lượng cũ. [1] [2]

Năm sau (680), Hành Kiệm tiếp tục nắm các cánh quân đi đánh dẹp. Quân Đường đóng trại ở Hình Khẩu thuộc Đại Châu, Hành Kiệm tung phản gián khuyên dụ Phục Niệm và Ôn Phó, khiến hai người nghi kỵ lẫn nhau. Phục Niệm sợ hãi, bí mật xin hàng, còn hứa lập công chuộc tội. Hành Kiệm không tiết lộ việc này, nhưng dâng mật biểu về triều. Mấy ngày sau, có bụi mù giăng trời kéo đến, lính do thám sợ hãi quay về thông báo, Hành Kiệm triệu tập ba quân, nói rằng: “Đây là Phục Niệm bắt Ôn Phó đến hàng, chẳng khác được. Nhưng nhận hàng cũng như đón địch, vẫn phải nghiêm túc phòng bị.” Rồi sai 1 sứ giả đơn độc ra đón và úy lạo. Ít lâu sau, Phục Niệm quả nhiên soái bộ thuộc trói Ôn Phó đến cửa quân xin nhận tội. [1] [2]

Quân Đường dẹp xong cuộc nổi dậy của người Đột Quyết, Đường Cao Tông cả mừng, sai Hộ bộ thượng thư Thôi Tri Đễ úy lạo quân đội. Thị trung Bùi Viêm đố kỵ công lao của Hành Kiệm, cùng tổng quản Trình Vụ Đĩnh, Trương Kiền Úc tâu lên rằng: “Phục Niệm bị Trình Vụ Đĩnh, Trương Kiền Úc áp sát bên sườn, lại chịu người Hồi Hột ở phía bắc sa mạc bức bách, cùng quẫn mới xin hàng.” Do vậy Hành Kiệm không được ghi công, còn Phục Niệm và Ôn Phó đều bị chém ở chợ. Ban đầu Hành Kiệm đã hứa cho Phục Niệm khỏi tội chết, đến nay than rằng: “Việc Hồn, Tuấn ngày trước [lower-alpha 12], xưa nay lấy làm xấu hổ. Chỉ sợ giết người xin hàng, sau này không còn ai chịu đến nữa.” Nhân đó Hành Kiệm xưng bệnh không ra ngoài nữa. [1] [2]

Nhờ công huân, Hành Kiệm được phong Văn Hỷ huyện công. Năm Vĩnh Thuần đầu tiên (682), A Sử Na Xa Bạc xưng khả hãn của Thập Tính Đột Quyết để nổi dậy, triều đình lại giáng chiếu lấy Hành Kiệm làm Kim Nha đạo Đại tổng quản, soái 10 tướng quân đi dẹp. Còn chưa lên đường thì vào ngày 28 tháng 4 ÂL (ngày 9 tháng 6) cùng năm, Hành Kiệm bệnh mất, hưởng thọ 64 tuổi. [6] [1] [2]